package day01

// day01
//
// 139. 单词拆分
//
// https://leetcode.cn/problems/word-break/
//
// ```go
func wordBreak(s string, wordDict []string) bool {
	//表示 s 的前 i 位是否可以用 wordDict 中的单词表示
	mp := map[string]bool{}
	for _, v := range wordDict {
		mp[v] = true
	}
	dp := make([]bool, len(s)+1)
	dp[0] = true
	for i := 1; i <= len(s); i++ {
		for j := 0; j < i; j++ {
			word := s[j:i]
			if dp[j] && mp[word] {
				dp[i] = true
				break
			}
		}
	}
	return dp[len(s)]
}

//```

// 198. 打家劫舍
//
// https://leetcode.cn/problems/house-robber/
//
// ```go
func rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	//dp[i]=max(dp[i-2]+nums[i], dp[i-1])
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	dp[1] = max(nums[0], nums[1])
	for i := 2; i < len(nums); i++ {
		dp[i] = max(dp[i-2]+nums[i], dp[i-1])
	}
	return dp[len(nums)-1]
}

//```

// 213. 打家劫舍 II
//
// https://leetcode.cn/problems/house-robber-ii/
//
// ```go
func rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	r1 := rob0(nums[:len(nums)-1])
	r2 := rob0(nums[1:])
	return max(r1, r2)
}
func rob0(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	dp[1] = max(nums[0], nums[1])
	for i := 2; i < len(nums); i++ {
		dp[i] = max(dp[i-2]+nums[i], dp[i-1])
	}
	return dp[len(nums)-1]
}

//```

// 337. 打家劫舍 III
//
//https://leetcode.cn/problems/house-robber-iii/
//
//```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rob(root *TreeNode) int {
	var dfs func(root *TreeNode) (int, int)
	dfs = func(node *TreeNode) (int, int) {
		if node == nil {
			return 0, 0
		}
		lRob, lNotRob := dfs(node.Left)
		rRob, rNotRob := dfs(node.Right)
		r1 := node.Val + rNotRob + lNotRob
		r2 := max(lRob, lNotRob) + max(rRob, rNotRob)
		return r1, r2
	}
	r1, r2 := dfs(root)
	return max(r1, r2)
}

//```
